package com.markus.code.exam.qushikeji;

import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;

import java.util.HashMap;
import java.util.Scanner;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/12 19:14
 * todo:
 */
public class Main {
    public static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String inStr = scanner.next();
            String aftStr = scanner.next();
            char []inorder = new char[inStr.length()];
            char []aftorder = new char[aftStr.length()];
            for (int i = 0; i < inorder.length; i++) {
                inorder[i] = inStr.charAt(i);
                aftorder[i] = aftStr.charAt(i);
            }
            Main demo = new Main();
            TreeNode root = demo.reBuildTree(inorder,aftorder);
            demo.printTree(root);
        }
    }
    private HashMap<Character,Integer> indexMap;
    private char[] aftorder;
    private TreeNode reBuildTree(char[] inorder,char []aftorder){
        if (inorder == null || inorder.length == 0 || aftorder == null || aftorder.length == 0){
            return null;
        }
        indexMap = new HashMap<>();
        for (int i=0;i<inorder.length;i++){
            indexMap.put(inorder[i],i);
        }
        this.aftorder = aftorder;
        return process(0,aftorder.length-1,0,inorder.length-1);
    }
    private TreeNode process(int aL,int aR,int iL,int iR){
        if (aL > aR){
            return null;
        }
        char rootValue = aftorder[aR];
        int index = indexMap.get(rootValue);
        TreeNode root = new TreeNode(rootValue);
        root.left = process(aL,index-1,iL,index-1);
        root.right = process(index,aR-1,index+1,iR);
        return root;
    }
    private void printTree(TreeNode root){
        if (root != null){
            System.out.print(root.val);
            printTree(root.left);
            printTree(root.right);
        }
    }
}
